package 算法;

/**
 * @author zhangmin
 * @create 2021-12-14 10:11
 * 位运算
 */
public class BitOperation05 {
    /**==============================================================================================================================================
     * JZ65 不用加减乘除做加法
     * 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
     * 两数相加，在各个二进制位上的结果：无进位和运算就是按位异或结果，进位就是与运算结果但是需要左移一位，因为进位影响下一位的运算
     *  */
    public int Add(int num1,int num2) {
        while (num2!=0){
            int c=(num1&num2)<<1;//进位
            num1^=num2;//num1记录无进位和
            num2=c;//num2记录进位
        }
        return num1;
    }
    /**==============================================================================================================================================
     * JZ15 二进制中1的个数
     * 输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
     * n&(n-1)消除n的最后一个1，循环消除直到n为0
     *  */
    public int NumberOf1(int n) {
        int count=0;
        while (n!=0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
    /**==============================================================================================================================================
     * JZ16 数值的整数次方
     * 实现函数 double Power(double base, int exponent)，求base的exponent次方。
     * 1、普通循环计算，超时
     * 2、快速幂：利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。循环取出exponent的二进制最后一位，当其为1时，结果成上base，在每一位上将base变成base的，
     *  */
    public double Power(double base, int exponent) {
        long n=exponent;
        double res=1.0;
        if (n<0){
            base=1/base;
            n=-n;
        }
        while (n!=0){
            if ((n&1)==1) {
                res*=base;
            }
            base*=base;
            n>>=1;//去掉n的最后一位
        }
        return res;
    }


    /**==============================================================================================================================================
     * JZ56 数组中只出现一次的两个数字
     * 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
     * 1、排序后遍历判断
     * 2、分类异或：如果把nums 中的所有元素全部异或起来，得到结果 x。使用位运算x & -x取出 x的二进制表示中最低位那个 1，设其为第 l 位，
     * 那么 x_1 和 x_2中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。
     * 这样一来，我们就可以把 nums中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数
     * 对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
     * 对于任意一个在数组 nums 中只出现了一次的元素，即 x_1和 x_2，它们会被包含在不同类中。
     *  */
    public int[] FindNumsAppearOnce (int[] array) {
        int xorsum=0; //异或和
        for (int a:array) {
            xorsum^=a;
        }
        //防止溢出
        int xor=(xorsum==Integer.MIN_VALUE?xorsum:xorsum&(-xorsum));
        int t1=0,t2=0;
        //分组异或
        for (int arr:array) {
            if ((arr&xor)!=0){
                t1^=arr;
            }else {
                t2^=arr;
            }
        }
        return t1<t2?new int[]{t1,t2}:new int[]{t2,t1};
    }

    /**==============================================================================================================================================
     * JZ64 求1+2+3+...+n
     * 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     * 1、递归：逻辑运算符的短路性质代替判断
     * 2、快速乘：A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟。其实就是将 B 二进制展开，
     * 如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i) ，即 A<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，这个方法也被称作「俄罗斯农民乘法」
     *  */
    public int Sum_Solution(int n) {
        boolean flag=n>0&&(n+=Sum_Solution(n-1))>0;
        return n;
    }
}
